package com.wenhao.leetcode.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 题目：https://leetcode-cn.com/problems/permutations-ii/
 *
 * 全排列2
 *
 *
 *
 * @author Wenhao Tong
 * @Description
 * @create 2021-06-28 11:01
 */
public class LeetCode47 {
    public static void main(String[] args) {
        LeetCode47 leetCode47 = new LeetCode47();
        List<List<Integer>> lists = leetCode47.permuteUnique(new int[]{1,1,2,3,4,4});
        for (List<Integer> list : lists) {
            for (Integer num : list) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        List<Integer> path = new ArrayList<>();
        dfs(path,nums,used);
        return result;
    }

    public void dfs(List<Integer> path,int[] nums,boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
        }
        // 利用used数组实现一个标准的递归回溯的过程
        for (int i = 0;i < nums.length;i++) {
            if (used[i]) {
                continue;
            }
            // 主要是看i-1有没有被使用过，如果已经使用过且当前的还是和他重复的话，那这个可以不用拍了
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]) {
                continue;
            }
            // 这三行是递归
            path.add(nums[i]);
            used[i] = true;
            dfs(path,nums,used);
            // 这两行是回溯
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

}
